Users of relational database management systems (DBMSs) retrieve and manipulate information in databases by specifying queries in a structured query language (SQL). The SQL is then compiled before execution.
Compilation includes a parsing process and an optimization process. In parsing, the DBMS typically parses the specified SQL into a tree of relational operators. The relational operators may specify how to implement the query.
The tree is optimized for efficient execution through the generation of an optimized tree of relational operators. This optimized tree is known as a query execution plan (plan). The plan is executed by a runtime engine in the DBMS to produce results to the user's query. Accordingly, the total response time to the user specifying the SQL includes the time spent in compilation and execution.
Queries can be categorized according to their complexity and cost. The complexity of a query represents the number of possible alternatives for implementing the query. For more complex queries, more alternatives may be explored during optimization. As such, the time spent during optimization is a function of the complexity of the user query (i.e., the number of joined entities).
One goal of optimization is to produce a query plan with a low cost. Queries are typically optimized under the assumption that more time spent during optimization results in lower cost queries.
The cost of a query is a reflection of how long the query takes to execute. Larger volumes of data take longer to execute than smaller volumes. As such, the time spent executing a query is a function of the volume of data processed.